home *** CD-ROM | disk | FTP | other *** search
/ Complete Linux / Complete Linux.iso / docs / apps / database / postgres / postgre4.z / postgre4 / src / lib / H / access / nbtree.h < prev    next >
Encoding:
C/C++ Source or Header  |  1992-08-27  |  4.8 KB  |  165 lines
  1. /*
  2.  *  btree.h -- header file for postgres btree access method implementation.
  3.  *
  4.  *    $Header: /private/postgres/src/lib/H/access/RCS/nbtree.h,v 1.8 1991/07/03 19:43:03 mao Exp $
  5.  */
  6.  
  7. /*
  8.  *  BTPageOpaqueData -- At the end of every page, we store a pointer to
  9.  *  both siblings in the tree.  See Lehman and Yao's paper for more info.
  10.  *  In addition, we need to know what sort of page this is (leaf or internal),
  11.  *  and whether the page is available for reuse.
  12.  *
  13.  *  Lehman and Yao's algorithm requires a ``high key'' on every page.  The
  14.  *  high key on a page is guaranteed to be greater than or equal to any key
  15.  *  that appears on this page.  Our insertion algorithm guarantees that we
  16.  *  can use the initial least key on our right sibling as the high key.  We
  17.  *  allocate space for the line pointer to the high key in the opaque data
  18.  *  at the end of the page.
  19.  *
  20.  *  Rightmost pages in the tree have no high key.
  21.  */
  22.  
  23. typedef struct BTPageOpaqueData {
  24.     PageNumber    btpo_prev;
  25.     PageNumber    btpo_next;
  26.     uint16        btpo_flags;
  27.  
  28. #define BTP_LEAF    (1 << 0)
  29. #define BTP_ROOT    (1 << 1)
  30. #define BTP_FREE    (1 << 2)
  31.  
  32. } BTPageOpaqueData;
  33.  
  34. typedef BTPageOpaqueData    *BTPageOpaque;
  35.  
  36. /*
  37.  *  ScanOpaqueData is used to remember which buffers we're currently
  38.  *  examining in the scan.  We keep these buffers locked and pinned and
  39.  *  recorded in the opaque entry of the scan in order to avoid doing a
  40.  *  ReadBuffer() for every tuple in the index.  This avoids semop() calls,
  41.  *  which are expensive.
  42.  */
  43.  
  44. typedef struct BTScanOpaqueData {
  45.     Buffer    btso_curbuf;
  46.     Buffer    btso_mrkbuf;
  47. } BTScanOpaqueData;
  48.  
  49. typedef BTScanOpaqueData    *BTScanOpaque;
  50.  
  51. /*
  52.  *  BTItems are what we store in the btree.  Each item has an index tuple,
  53.  *  including key and pointer values.  In addition, we must guarantee that
  54.  *  all tuples in the index are unique, in order to satisfy some assumptions
  55.  *  in Lehman and Yao.  The way that we do this is by generating a new OID
  56.  *  for every insertion that we do in the tree.  This adds four bytes to the
  57.  *  size of btree index tuples.
  58.  */
  59.  
  60. typedef struct BTItemData {
  61.     OID            bti_oid;
  62.     IndexTupleData        bti_itup;
  63. } BTItemData;
  64.  
  65. typedef BTItemData    *BTItem;
  66.  
  67. /*
  68.  *  BTStackData -- As we descend a tree, we push the (key, pointer) pairs
  69.  *  from internal nodes onto a private stack.  If we split a leaf, we use
  70.  *  this stack to walk back up the tree and insert data into parent nodes
  71.  *  (and possibly to split them, too).  Lehman and Yao's update algorithm
  72.  *  guarantees that under no circumstances can our private stack give us
  73.  *  an irredeemably bad picture up the tree.  Again, see the paper for
  74.  *  details.
  75.  */
  76.  
  77. typedef struct BTStackData {
  78.     PageNumber        bts_blkno;
  79.     OffsetIndex        bts_offset;
  80.     BTItem            bts_btitem;
  81.     struct BTStackData    *bts_parent;
  82. } BTStackData;
  83.  
  84. typedef BTStackData    *BTStack;
  85.  
  86. /*
  87.  *  We need to be able to tell the difference between read and write
  88.  *  requests for pages, in order to do locking correctly.
  89.  */
  90.  
  91. #define    BT_READ        0
  92. #define    BT_WRITE    1
  93.  
  94. /*
  95.  *  Similarly, the difference between insertion and non-insertion binary
  96.  *  searches on a given page makes a difference when we're descending the
  97.  *  tree.
  98.  */
  99.  
  100. #define BT_INSERTION    0
  101. #define BT_DESCENT    1
  102.  
  103. /*
  104.  *  In general, the btree code tries to localize its knowledge about page
  105.  *  layout to a couple of routines.  However, we need a special value to
  106.  *  indicate "no page number" in those places where we expect page numbers.
  107.  */
  108.  
  109. #define P_NONE        0
  110.  
  111. /*
  112.  *  Strategy numbers -- ordering of these is <, <=, =, >=, > 
  113.  */
  114.  
  115. #define BTLessStrategyNumber        1
  116. #define BTLessEqualStrategyNumber    2
  117. #define BTEqualStrategyNumber        3
  118. #define BTGreaterEqualStrategyNumber    4
  119. #define BTGreaterStrategyNumber        5
  120. #define BTMaxStrategyNumber        5
  121.  
  122. /*
  123.  *  When a new operator class is declared, we require that the user supply
  124.  *  us with an amproc procudure for determining whether, for two keys a and
  125.  *  b, a < b, a = b, or a > b.  This routine must return < 0, 0, > 0,
  126.  *  respectively, in these three cases.  Since we only have one such proc
  127.  *  in amproc, it's number 1.
  128.  */
  129.  
  130. #define BTORDER_PROC    1
  131.  
  132. /* public routines */
  133. char            *btgettuple();
  134. InsertIndexResult    btinsert();
  135.  
  136. /* private routines */
  137. InsertIndexResult    _bt_doinsert();
  138. InsertIndexResult    _bt_insertonpg();
  139. OffsetIndex        _bt_pgaddtup();
  140. ScanKey            _bt_mkscankey();
  141. BTStack            _bt_search();
  142. BTStack            _bt_searchr();
  143. void            _bt_relbuf();
  144. Buffer            _bt_getbuf();
  145. void            _bt_wrtbuf();
  146. void            _bt_wrtnorelbuf();
  147. bool            _bt_skeycmp();
  148. OffsetIndex        _bt_binsrch();
  149. OffsetIndex        _bt_firsteq();
  150. Buffer            _bt_getstackbuf();
  151. RetrieveIndexResult    _bt_first();
  152. RetrieveIndexResult    _bt_next();
  153. RetrieveIndexResult    _bt_endpoint();
  154. bool            _bt_step();
  155. bool            _bt_twostep();
  156. StrategyNumber        _bt_getstrat();
  157. bool            _bt_invokestrat();
  158. BTItem            _bt_formitem();
  159. bool            _bt_goesonpg();
  160. void            _bt_regscan();
  161. void            _bt_dropscan();
  162. void            _bt_adjscans();
  163. void            _bt_scandel();
  164. bool            _bt_scantouched();
  165.